2020.11.20 模拟赛

T1\text{T1}

Subtask 1 40 pts

直接暴力模拟即可。

Subtask 2 100 pts

不难发现重要的只有 A+BA+BCC,而且可以发现 A+B+CA+B+C 是一个定值。然后你发现答案其实就是 2k×C(modA+B+C)2^k\times C\pmod {A+B+C},快速幂即可。

T2\text{T2}

Subtask 1 & 2 30 pts

直接暴力应该是可以的。

Subtask3 50 pts

可以每次建一个图,原点往扑克连一条流量为 11 的边,扑克往面值分别连一条流量为 11 的边,面值往汇点连一条容量为 11 的边。每次查询 [l,r][l,r] 的话直接只把 [l,r][l,r] 这段面值的点往汇点连边即可。

时间复杂度 懂得都懂。

Subtask4 10 pts

直接前缀和判断即可。

Subtask5 100 pts

将每个扑克的 u,vu,v 相连,不难看出是一个树的时候一定不能满足全都选出来,如果里面有环则一定可以满足全都能选出来。

于是问题就是判定一个区间对应的点里是否包含树,直接离线下来扫描线即可。

时间复杂度 Θ(nlogn)\Theta(n\log n)

T3\text{T3}

思路1:树状数组

我们考虑对于点vv算出它的值那么就是:

t=1i1(xtdis[ut,v]×kt)\sum_{t=1}^{i-1} (x_t-dis[u_t,v]\times k_t)

=t=1i1(xt(deep[v]deep[ut])×kt)=\sum_{t=1}^{i-1} (x_t-(deep[v]-deep[u_t])\times k_t)

=t=1i1(xt+deep[ut]×kt)deep[v]×t=1i1kt=\sum_{t=1}^{i-1} (x_t+deep[u_t]\times k_t)-deep[v]\times \sum_{t=1}^{i-1} k_t

但是我们发现这个东西需要满足utu_t1v1\to v的路径上,怎么办呢?很简单,我们可以利用dfsdfs的特性解决即可,然后这个东西直接用两个树状数组维护即可。

因为一个操作会加入删除各一次,所以总时间复杂度为Θ(mlogm+n)\Theta(m\log m+n)

思路2:线段树

其实很套路,我们发现这个东西是给子树内加上一个等差数列(不是很严谨,大家意会一下),跟这道题有些相似。

于是就十分套路了。我们直接用线段树维护一个差分数组,每次操作就相当于给uu节点加上xx,给子树内其他节点加上k-k

查询操作就相当于询问1u1\to u的路径和。

时间复杂度为Θ(mlog2n+n)\Theta(m\log ^2n+n)

T4\text{T4}

Subtask 1

这个怎么暴力都可以吧

Subtask 2

还是暴力,加上记忆化就可以了。

因为 m=2m=2 好写很多。

Subtask 3    k=0~~~k=0

f0(n)=pi=n[i,j(i=j)gcd(pi,pj)=1]f_0(n)=\sum_{\prod p_i=n} [\forall i,j(i\not=j) \gcd(p_i,p_j)=1]

τ(n)\tau(n)nn 的不同质因数的个数。

因为要求任意 pi,pj(i=j)p_i,p_j(i\not=j)gcd(pi,pj)=1\gcd(p_i,p_j)=1 , 那么相同的质因数只会全部在其中一个 pip_i中。

每种不同的质因数有 mm 种选法,那么 f0(n)=mτ(n)f_0(n)=m^{\tau(n)}

可以看出,f0(n)f_0(n) 是一个积性函数。

具体实现可以欧拉筛出最小质因子,对询问的 nn 分解质因数后将每一部分乘起来。

Subtask 4    k=0~~~k\not =0

fk(n)=pi=nfk1(pi)f_k(n)=\sum_{\prod p_i=n} \prod f_{k-1}(p_i)

因为 f0(n)f_0(n) 是一个积性函数,可以猜测 fk(n)f_k(n) 也是一个积性函数。

考虑数学归纳法:

  1. k=0k=0 显然

  2. k=0k\not=0,假设 fk1f_{k-1} 为积性函数,对于任意互质两数 n,mn,m 有:

    fk(n)×fk(m)=pi=nfk1(pi)×qi=mfk1(qi)f_{k}(n) \times f_{k}(m) =\sum_{\prod p_i=n} \prod f_{k-1}(p_i) \times \sum_{\prod q_i=m} \prod f_{k-1}(q_i)

                             =pi=n,qi=mfk1(pi)×fk1(qi)~~~~~~~~~~~~~~~~~~~~~~~~~=\sum_{\prod p_i=n ,\prod q_i=m} \prod f_{k-1}(p_i) \times \prod f_{k-1}(q_i)

           =piqi=nmfk1(pi×qi)~~~~~~~=\sum_{\prod p_i \prod q_i=nm} \prod f_{k-1}(p_i \times q_i)

    =fk(nm)                         =f_k(nm)~~~~~~~~~~~~~~~~~~~~~~~~~

现在只需要求出质数的幂的函数值即可。

fk(pw)=pi=wfk1(ppi)f_k(p^w)=\sum_{\sum p_i=w} \prod f_{k-1}(p^{p_i})

发现 fk(pw)f_k(p^w)pp 的值无关,所以可以提取出一个递推式:

fk,w=pi=wfr1,pif_{k,w}=\sum_{\sum p_i=w} \prod f_{r-1,p_i}

这个我也不知道怎么递推,不过给了分的...

tr 巨佬提出了一个 O(kmlog2n)\mathcal O(km\log^2n) 的做法 ?

Subtask 5

发现 f0={1,m,m....}f_0 = \{1,m,m....\} , fk=(f0)mkf_k=(f_0)^{m^k}

观察每一项,发现除了第一项系数都为 mm

可以钦定 mm 的个数为 ii ,那么对系数的贡献便为 mim^i

再考虑方案数,首先你得从 mkm^kf0f_0 中选出 ii 个来提供指数,然后用插板法算出分配指数的方案。

答案为:

fk,w=i=1wmi(mki)(w1i1)f_{k,w}=\sum_{i=1}^w m^i \binom{m^k}{i} \binom{w-1}{i-1}

这样单次询问可以暴力算组合数,是 O(w)\mathcal O(\sum w) 的,比 O(logn)\mathcal O(\log n) 小。

瓶颈在于求 mkm^k ,复杂度 O(qlogmod)\mathcal O(q \log \text{mod})

当然你用 ** 函数的知识会更好理解一些。